//
//  200. 岛屿数量.swift
//  手撕代码
//
//  Created by xiaoZuDeMeng on 2024/2/22.
//

import Foundation

//给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
//
//岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
//
//此外，你可以假设该网格的四条边均被水包围。
//
//
//
//示例 1：
//
//输入：grid = [
//  ["1","1","1","1","0"],
//  ["1","1","0","1","0"],
//  ["1","1","0","0","0"],
//  ["0","0","0","0","0"]
//]
//输出：1
//示例 2：
//
//输入：grid = [
//  ["1","1","0","0","0"],
//  ["1","1","0","0","0"],
//  ["0","0","1","0","0"],
//  ["0","0","0","1","1"]
//]
//输出：3
//
//
//提示：
//
//m == grid.length
//n == grid[i].length
//1 <= m, n <= 300
//grid[i][j] 的值为 '0' 或 '1'

func 岛屿数量(_ grid: [[Character]]) -> Int {
    return 0
}

func numIslands(_ grid: [[Character]]) -> Int {
    if grid.count <= 0 {
        return 0
    }

    var resultCount = 0
    var grid = grid
    let row = grid.count
    let culomn = grid[0].count

    //双重循环遍历
    for i in 0..<row {
        for j in 0..<culomn {
            if grid[i][j] == "1" {
                //针对每一个为1的节点进行深度优先搜索
                resultCount += 1  //每深度优先搜索一次后，周边的为1的都会被触达(上下左右)，并且内部会设置为0
                numDFS(&grid, i, j)
            }
        }
    }

    return resultCount
}

//核心深度优先算法逻辑，其内部使用递归方式进行上，下，左，右遍历
func numDFS(_ grid: inout [[Character]], _ currRow: Int, _ currColumn: Int) {
    let originRow = grid.count
    let Originculomn = grid[0].count

    if currColumn < 0 || currRow < 0 || currRow >= originRow || currColumn >= Originculomn || grid[currRow][currColumn] ==  "0" {
        return
    }

    grid[currRow][currColumn] = "0"
    //递归进行搜索
    numDFS(&grid, currRow, currColumn-1) //上
    numDFS(&grid, currRow, currColumn+1) //下
    numDFS(&grid, currRow-1, currColumn) //左
    numDFS(&grid, currRow+1, currColumn) //右
}
